package com.jack.leetcode.eachproblem_2020;

import java.util.Arrays;

/**
 * Created by zhang_j on 2020/10/24
 */
public class 视频拼接 {

    public static void main(String[] args) {
        int[][] a = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
        System.out.println(videoStitching(a, 10));
    }

    public static int videoStitching(int[][] clips, int T) {
        int n = clips.length;
        int[] dp = new int[T + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        dp[0] = 0;
        for(int i = 1;i <= T;i++){
            for (int[] clip : clips) {
                if(clip[0] < i && i <= clip[1]){
                    dp[i] = Math.min(dp[i], dp[clip[0]] + 1);
                }
            }
        }
        return dp[T] == Integer.MAX_VALUE - 1 ? -1 : dp[T];
    }
}
